1. Field of Invention
This invention relates to methods and systems for encoding and decoding data using run prediction.
2. Description of Related Art
The world of information theory that deals with binary signals is aware of arithmetic encoding methods. An arithmetic encoding method is an entropy encoding method that is intrinsically reversible (i.e., lossless). Also, arithmetic encoding is an ideal encoding method because it stores the information source. In contrast, alias encoding methods rely on non-stored information sources.
In arithmetic encoding, the stored information is divided into unequal length sections that correspond to the occurrence probability of each symbol in the data. The method assigns a symbol to each section. Sections which are able to be divided have coordinates that are acquired by repetitive recursive division and are expressed as binary numbers. The method encodes those coordinates within the corresponding section.
In comparison to encoding methods which require block encoding of specific codes and information source symbols, arithmetic encoding methods have several advantages. Such advantages include: reduced memory requirements, high efficiency encoding and the ability to easily perform adaptive encoding. An arithmetic encoding method can also compress information to a level that is nearest to the entropy of the information. Arithmetic encoding is also particularly suitable for Markov information source encoding.
Several different types of encoders have been proposed for arithmetic encoding methods. For example, a Q encoder, a MEL encoder and a Mini-Max encoder have been proposed. A QM encoder is also known as an improvement over other arithmetic encoders. QM encoders are commonly used in both color still image encoding (such as JPEG) and binary image encoding (JBIG) standards.
A QM encoder encodes binary information sources. Therefore, prior to encoding multi-level information sources, the multi-level information source requires pre-processing to make it binary. This conversion generally increases the number of symbols to be encoded. However, it is possible to convert to a binary series without increasing the amount of information.
The design of a QM encoder is explained in detail in the regulations of JPEG and JBIG. However, for the sake of comparison with the later-explained present invention, the QM encoder scheme is explained briefly using FIG. 12. An explanation of the structure of an arithmetic decoding type of entropy decoder is omitted here because it is practically identical to the structure of an entropy encoder.
The QM encoder 101 includes an arithmetic calculator 102 and a development probability generating means 103. The development probability generating means 103 functions as a state storage device. A state parameter table is written in the development probability generating means 103 to determine a symbol occurrence rate for the encoding process. The state parameters in the state parameter table are specified by the input state signals 106. The arithmetic calculator 102 outputs a readout address during the update of the calculated parameters. The development probability generating means 103 outputs state parameters to the arithmetic calculator 102 in accordance with the readout address. The arithmetic calculator 102 compresses the input data 104 into encoding data based upon the data input into the arithmetic calculator 102. Additionally, state signals 106 are input to the development probability generating means 103. The state signals 106 are used to increase the compression rate. The state signals 106 include, for example, reference pixel data such as is referenced by a Markov model.
The control routine of the QM encoder shown in FIG. 12 is described in the flowchart in FIG. 13. The flowchart of FIG. 13 starts and proceeds to step S100 where a value 0.times.0000 is stored in register C, a value of 0.times.FFFF is stored in register A and an index ST is initialized. Next, in step S101, one bit of the input data is fetched. In step S102, the control routine determines whether the input bit is a numerically superior symbol or a numerically inferior symbol. The numerically superior symbol is arbitrarily designated as either a "0" or a "1" and the numerically inferior symbol is designated as the other of a "0" or "1". When the input bit is the numerically superior symbol the control routine continues to step S103. When the input bit is a numerically inferior symbol the control routine proceeds to step S106.
The occurrence probability of a numerically inferior symbol can be obtained by referring to a probability estimate table LSZ using the index ST. The occurrence probability of the numerically superior symbol can be obtained by subtracting the probability of the numerically inferior symbol from the contents of register A.
In step S103, the occurrence probability of the numerically superior symbol is stored in register A. Then, in step S104, the control routine determines whether the highest ranking bit in register A is "1". If it is "1" then the control routine continues to step S105 and if it is "0" then the control routine jumps to step S114. In step S105, the index ST, for encoding the next symbol, is set using the probability estimate table NMPS using the index ST.
In step S106, the occurrence probability of a numerically inferior symbol is stored in register A. Then, in step S107, the value in register A is added to the value in register C and the sum is stored in register C. In step S108, the control routine determines whether the probability estimate table SWITCH outputs a "1" using the index ST. If, in step S108, the probability estimate table SWITCH outputs a "1" then the control routine continues to step S109 where the control routine changes the numerically superior symbol.
If, in step S108, the probability estimate table SWITCH does not output a "1", then the control routine jumps to step S110. In step S110, the index ST is set to the output of a probability estimate table NLPS using the index ST and the control routine continues to step S111.
In step S111, registers A and C are shifted one bit to the left. Then in step S112, the highest bit that has flowed out of register C is output as a code. The control routine then continues to step S113, where the control routine determines whether the highest bit in register A is "1". If, in step S113, the control routine determines that the highest bit in the register A is "1" then the control routine returns to step S111. If, however, the control routine determines that the highest bit in register A is not "1" then the control routine continues to step S114. In step S114, the control routine determines whether the current symbol is the last symbol in the input bit series. If in step S114, the control routine determines that the current symbol is not the last symbol in the input bit series then the control routine returns to step S101. If, in step S114 the control routine determines that the current symbol is the last symbol in the input bit series then the control routine returns control to the environment in which the control routine of FIG. 13 operates.
Thus, as shown in FIG. 13, the QM encoder 101 encodes the input bit series using probability estimate tables LSZ, NMPS and NLPS.
While the arithmetic encoding method of the QM encoder has a good encoding efficiency, the encoding speed is slow because the encoding is performed one bit at a time. In comparison, the encoding method of the Lempel-Ziv system has superior utility because the encoding speed is much faster. However, the speed benefits of the Lempel-Ziv system are significantly overshadowed by the QM encoder because the QM encoder has a much higher encoding efficiency. Conventional encoding technology does not have an encoding efficiency which is approximately as good as the arithmetic encoding method and which also has an encoding speed which is approximately as fast as the Lempel-Ziv system.